#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 100    // 数组最大长度
#define MAX_RESULT 1000// 最大排列数（n! ≤ 10! = 3628800，按需调整）

// 单个排列（存储字符串元素）
typedef struct {
    char* elements[MAX_LEN]; // 排列中的元素
    int len;                 // 排列长度
} Permutation;

// 结果集（存储所有全排列）
typedef struct {
    Permutation* items; // 排列数组
    int count;          // 已存储排列数
    int capacity;       // 结果集容量
} ResultSet;

/**
 * 初始化结果集
 */
ResultSet* result_set_init(int capacity) {
    ResultSet* rs = (ResultSet*)malloc(sizeof(ResultSet));
    rs->items = (Permutation*)malloc(capacity * sizeof(Permutation));
    rs->count = 0;
    rs->capacity = capacity;
    return rs;
}

/**
 * 向结果集添加一个排列（深拷贝，避免原数组修改影响结果）
 */
void result_set_add(ResultSet* rs, const char* array[], int len) {
    if (rs->count >= rs->capacity) {
        fprintf(stderr, "结果集溢出！请增大MAX_RESULT\n");
        return;
    }
    Permutation* p = &rs->items[rs->count++];
    p->len = len;
    for (int i = 0; i < len; i++) {
        p->elements[i] = (char*)malloc(strlen(array[i]) + 1);
        strcpy(p->elements[i], array[i]);
    }
}

/**
 * 交换数组中两个位置的元素（辅助函数）
 */
void swap(char* array[], int i, int j) {
    char* temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

/**
 * Heap算法递归核心（对应Python的recursive函数）
 * @param array: 待排列数组（会被就地修改，通过递归回溯恢复）
 * @param last: 当前处理的末尾索引（初始为len(array)-1）
 * @param len: 数组长度
 * @param rs: 结果集
 */
void heap_recursive(char* array[], int last, int len, ResultSet* rs) {
    if (last == 0) {
        // 递归终止：已生成一个全排列，添加到结果集
        result_set_add(rs, (const char**)array, len);
        return;
    }

    for (int i = 0; i <= last; i++) {
        // 递归处理前last个元素（last-1为新末尾）
        heap_recursive(array, last - 1, len, rs);

        // 根据last的奇偶性交换元素（Heap算法核心规则）
        if (last & 1) {
            // last为奇数：交换i和last位置
            swap(array, i, last);
        } else {
            // last为偶数：交换0和last位置
            swap(array, 0, last);
        }
    }
}

/**
 * Heap算法全排列（对应Python的permutations函数）
 * @param array: 输入字符串数组（const，避免外部修改）
 * @param len: 数组长度
 * @return: 结果集（需调用者释放）
 */
ResultSet* permutations_heap(const char* array[], int len) {
    if (len <= 0 || len > MAX_LEN) {
        fprintf(stderr, "数组长度需在1~%d之间\n", MAX_LEN);
        return NULL;
    }

    // 深拷贝输入数组（避免修改原数组，同时支持就地交换）
    char** copy_array = (char**)malloc(len * sizeof(char*));
    for (int i = 0; i < len; i++) {
        copy_array[i] = (char*)malloc(strlen(array[i]) + 1);
        strcpy(copy_array[i], array[i]);
    }

    // 初始化结果集
    ResultSet* rs = result_set_init(MAX_RESULT);

    // 调用递归核心函数（初始last = len-1）
    heap_recursive(copy_array, len - 1, len, rs);

    // 释放拷贝的数组内存
    for (int i = 0; i < len; i++) {
        free(copy_array[i]);
    }
    free(copy_array);

    return rs;
}

/**
 * 打印结果集（模拟Python列表输出格式）
 */
void print_result(ResultSet* rs) {
    for (int i = 0; i < rs->count; i++) {
        Permutation* p = &rs->items[i];
        printf("[");
        for (int j = 0; j < p->len; j++) {
            printf("\"%s\"", p->elements[j]);
            if (j != p->len - 1) {
                printf(", ");
            }
        }
        printf("]\n");
    }
}

/**
 * 释放结果集内存
 */
void result_set_free(ResultSet* rs) {
    for (int i = 0; i < rs->count; i++) {
        Permutation* p = &rs->items[i];
        for (int j = 0; j < p->len; j++) {
            free(p->elements[j]);
        }
    }
    free(rs->items);
    free(rs);
}

// 测试主函数（与Python测试用例一致）
int main() {
    // 测试数组：['A', 'B', 'C', 'D']
    const char* array[] = {"A", "B", "C", "D"};
    int len = sizeof(array) / sizeof(array[0]);

    // 调用Heap算法全排列
    ResultSet* rs = permutations_heap(array, len);

    // 打印结果（与Python输出顺序完全一致）
    printf("Heap算法全排列结果（共%d个）：\n", rs->count);
    print_result(rs);

    // 释放内存
    result_set_free(rs);

    return 0;
}